home *** CD-ROM | disk | FTP | other *** search
/ HPAVC / HPAVC CD-ROM.iso / TPTUTR~1.ZIP / PASCAL19.TXT < prev    next >
Text File  |  1996-03-21  |  13KB  |  305 lines
  1.                         Turbo Pascal for DOS Tutorial
  2.                             by Glenn Grotzinger
  3.                            Part 19: Binary Trees
  4.                  copyright (c) 1995-96 by Glenn Grotzinger
  5.  
  6. OK.  I stated no real problem that needed solving earlier, so we will start
  7. getting into some new material.  This is an extension to part 18, in a small
  8. way, since it involves pointered structures similar to the linked lists,
  9. but the procedures for handling them are much different, so I am covering
  10. them in a seperate section.
  11.  
  12. What is a Binary Tree?
  13. ======================
  14. A binary tree is a set of nodes with 2 possible paths for each node, left
  15. or right.  Hence, a binary tree node would look something like this:
  16.  
  17. type
  18.   nodeptr = ^node;
  19.   node = record
  20.     ourinfo: integer;
  21.     left, right: nodeptr;                                            
  22.   end;
  23.  
  24. Conceptually (my best low ASCII rendering, trust me!), a binary tree would
  25. look something like this.  We can see from below that the possible paths of
  26. those two directions are any numerous.  As with the linked lists, nil ends
  27. the path (knowing, it is probably garbled, but....).
  28.  
  29.                             NODE
  30.                    _________/  \_________
  31.                   /                      \
  32.                NODE                      NODE
  33.            ____/  \____              ____/  \____
  34.           /            \            /            \
  35.        NODE            nil        nil             NODE
  36.    ____/  \____                               ____/  \____
  37.   /            \                             /            \
  38. nil           nil                         NODE           nil
  39.                                       ____/  \____
  40.                                      /            \
  41.                                   NODE            nil
  42.                               ____/  \____
  43.                              /            \
  44.                            nil           nil
  45.  
  46.  
  47. Rules of a Binary Tree
  48. ======================
  49. Now that we see what the basic idea of a binary tree is, we will now study
  50. the rules for it.  The basic rules of a binary tree is the following for
  51. any node in a binary tree commonly used for the purpose that they are used
  52. for a lot of times -- as a binary search tree or BST.  Any program code
  53. in this section will make use of BSTs...:
  54.  
  55.         1) values smaller than the value currently stored in a questioned
  56.            node goes to the left.
  57.         2) values larger than the value currently stored in a questioned
  58.            node goes the right.
  59.         3) values which are equal to other values in the tree are not placed
  60.            into the tree.
  61.  
  62. Let us see this by manually examining how we might build a small binary tree.
  63.  
  64. Example of a Binary Tree Manual Build
  65. =====================================
  66. Let us examine how we would build a binary tree for a set of values and
  67. how a program would traverse the tree with a very short example.
  68.  
  69. 1) Let us start examining a tree build with a value set data of 27, 54,
  70.    32, 18, and 5.
  71.    a) 27 is naturally the first or root node of the tree.  There is no
  72.       issue there.
  73.    b) 54 > 27 so 54 would go to the right.  Our resultant tree looks now
  74.       like this:
  75.                                  27
  76.                                    \
  77.                                     54
  78.  
  79.    c) 32 > 27.  So we would move to the right.  Now we see 54 as the main
  80.       node  32 < 54, so we would go to the left.  So the resultant tree
  81.       after this addition looks like this:
  82.  
  83.                                  27
  84.                                    \
  85.                                     54
  86.                                    /
  87.                                  32
  88.  
  89.    d) 18 < 27.  So we would move to the left.  So our tree looks like this:
  90.  
  91.                                  27
  92.                                 /  \
  93.                               18    54
  94.                                    /
  95.                                  32
  96.  
  97.    e) 5 < 27.  So we would move to the left.  Now we see 18 as the current
  98.       node.  5 < 18.  Then we would move to the left again.  So the final
  99.       binary tree for those 5 values looks like this:
  100.  
  101.                                  27
  102.                                 /  \
  103.                               18    54
  104.                              /     /
  105.                            5     32
  106.  
  107. This is a reasonable binary tree structure.  Any paths not used are
  108. set to nil in the process.  We should see now how binary trees are
  109. constructed.
  110.  
  111. 2) Now lets study traversal of the tree.  It would depend on if we
  112. visit the actual node first or last.  (I will give a detailed explanation
  113. of that last statement later.)  Normally, as a standard, it's good to
  114. use the left side first.  Therefore, lets look at the tree built in #1.
  115.  
  116. The order the numbers would come up in is 5-18-27-32-54 on a basis that we
  117. handle or visit the head node of the tree last in moving through the binary
  118. tree. If you remember the discussion of the array binary search, we had to
  119. sort the data to accomplish it.  Here it is taken care of already for us.
  120.  
  121. Basic Idea of Programming for Binary Trees
  122. ==========================================
  123. You may have figured out already from our preliminary discussions, that
  124. recursion is a _major_ staple of binary tree programming (read ALWAYS use
  125. it!).  Note that a binary tree can be divided up into smaller and smaller
  126. trees, hence our ability to use recursion.  Any functions involved almost
  127. always ends up using some order of the following pseudocode, assuming a
  128. name of PROCEDURE for the procedure:
  129.  
  130. PERFORM PROCEDURE ON LEFT SIDE OF TREE
  131. PERFORM ACTION ON ROOT NODE (the top node of the tree)
  132. PERFORM PROCEDURE ON RIGHT SIDE OF TREE
  133.  
  134. We will see this idea be paramount in all the code we use.  If you have
  135. noticed in your previous work about recursion, there is always a control
  136. statement present.  Here, it will always be searching for the nil nodes.
  137. *ALWAYS* remember to replace the nil nodes if they come up....binary
  138. search trees are the perferred method generally, for setting up searches.
  139.  
  140. program binary_tree_example;
  141.  
  142.   type
  143.     nodeptr = ^node;
  144.     node = record
  145.       somedata: integer;
  146.       left, right: nodeptr;
  147.     end;
  148.  
  149.   var
  150.     tree: nodeptr;
  151.     afile: text;
  152.     i: integer;
  153.  
  154.   procedure deletetree(var tree: nodeptr);
  155.      { This procedure is a function designed to remove a binary tree
  156.        from memory }
  157.  
  158.     begin
  159.       { Given the background information, and other procedures as examples,
  160.         you should be able to come up with this one }
  161.     end;
  162.  
  163.   procedure inserttree(anumber: integer; var tree: nodeptr);
  164.      { This procedure is a function designed to create a binary tree
  165.        in memory by inserting a node in the proper position in the tree }
  166.  
  167.     begin
  168.       if tree = nil then
  169.         begin
  170.           new(tree);
  171.           tree^.somedata := anumber;
  172.           tree^.left := nil;
  173.           tree^.right := nil;
  174.         end
  175.       else
  176.         begin
  177.           if anumber > tree^.somedata then
  178.             inserttree(anumber, tree^.right);
  179.           if anumber < tree^.somedata then
  180.             inserttree(anumber, tree^.left);
  181.         end;
  182.     end;
  183.  
  184.   procedure searchthrutree(anumber: integer; tree: nodeptr);
  185.     { This procedure is designed to search through a binary tree for a
  186.       particular value given in the variable anumber. }
  187.     begin
  188.       { Given the background information and other procedures as examples,
  189.         you should be able to come up with this one. }
  190.     end;
  191.  
  192.   procedure writeouttree(tree: nodeptr);
  193.     { This procedure outputs a binary tree. }
  194.     begin
  195.       if tree <> nil then
  196.         begin
  197.           writeouttree(tree^.left);
  198.           write(afile, tree^.somedata, ',');
  199.           writeouttree(tree^.right);
  200.         end;
  201.     end;
  202.  
  203.   begin
  204.     randomize;
  205.     tree := nil;
  206.     { the last statement is required for the nil markers set up via the
  207.       BST procedures listed above }
  208.  
  209.     assign(afile, 'BTEST.TXT');
  210.     rewrite(afile);
  211.     writeln(memavail, ' bytes available before tree creation.');
  212.     for i := 1 to 10 do
  213.       inserttree(random(5)+1, tree);  {This creates the tree. }
  214.     writeln(memavail, ' bytes available after tree created.');
  215.     for i := 1 to 10 do
  216.       searchthrutree(random(5)+1, tree);
  217.     writeln(afile);
  218.     writeln(afile);
  219.     writeln(afile, 'I will now output the binary tree for the example.');
  220.     writeouttree(tree);
  221.     writeln;
  222.     close(afile);
  223.     writeln('Now deleting tree out of memory');
  224.     deletetree(tree);
  225.     writeln(memavail, ' bytes available after tree deletion.');
  226.   end.
  227.  
  228. This is a whole program for working with a binary tree.  I purposely left
  229. out 2 of the procedures, because the background information I gave earlier,
  230. plus pointer logic you should have learned from part 18 should allow you to
  231. logically come up with it.  Do like I recommended in part 18 and draw it
  232. out.  Example code is often not available for many problems, but the
  233. information _is_ there to be used.  To program it is a needed skill to be
  234. able to figure out things on your own given some information.  Code should
  235. not be handed out readily, IMO, unless there is no other way.
  236.  
  237. Practice Programming Problem #19
  238. ================================
  239. One noted thing I have noticed with the binary search tree method especially,
  240. is that searches can be done very quickly with any kind of data -- working
  241. with arrays have a small way of being kludgy.  Here we will see an example.
  242.  
  243. You need to create a binary data file named SOMEWRDS.DAT which should
  244. contain 50 non-duplicated words, randomly defined (do not alphabetize them)
  245. out of 70 total words in the file.
  246.  
  247. Allow users to type words into the keyboard, until they type the word
  248. "quit".  Case-sensitivity should not matter in any usage of words.
  249. Write out to the user whether the word they typed was found in your
  250. database or not.
  251.  
  252. Do not be concerned with reporting of run-time errors.  Do be concerned,
  253. though, with the removal of the final binary-tree you use.
  254.  
  255. Also for the delete code you write for binary trees, explain why your
  256. code does what it is supposed to do.
  257.  
  258. Note
  259. ----
  260. 1) Exercise prudent practice as programmers.  In the event it was not
  261. covered, accuracy is a programmer's #1 concern, followed by efficiency
  262. in speed, memory usage, and disk usage.
  263. 2) This program should be friendly to the user, letting the user know
  264. precisely what is going on in all cases, even if a common error occurs,
  265. and cleaning up anything that may be of a problematic nature from those
  266. errors.  You should have enough experience from previous parts to be
  267. able to determine what those errors are you would commonly encounter here.
  268. 3) The goal here for this program is to create a high-quality application.
  269.  
  270. Final Statements for this Part
  271. ==============================
  272. I know many people may wish to someday release their creations to the public,
  273. or make programs for themselves or other's general usage. This is why I am
  274. being so vague now about describing programs, and will be from now on.
  275. Creativity and neatness is one of the major qualities that need to be
  276. developed by those who program.
  277.  
  278. Also for all who program: The way to solve the problem is not always handed
  279. to you.  You have to identify problems that are encountered, sit down and
  280. solve them.  I estimate I'm probably 4-6 parts away from completing this
  281. whole tutorial, and 2 parts away from completing the parts of the tutorial
  282. regarding conventional Pascal programming.  By now, most, if not all the
  283. tools have been presented for you to do this, and not need me to give you
  284. clues, and point you in the direction of what to do to solve the problem.
  285. Most if not all problems you will encounter in normal programming practice
  286. anywhere are normally presented in the form that this one is in -- a
  287. statement of what the program is expected to do.
  288.  
  289. In short, I feel those who have been new programmers that have been following
  290. my tutorial from part 1 are about ready for the *REAL* world of programming.
  291. <grin>
  292.  
  293. Next Time
  294. ---------
  295. I will cover several short random topics, which some of which may be
  296. suggested by those who e-mail me.  I know I will cover hooking interrupts,
  297. calling an interrupt procedure, and linking an OBJ into Pascal code,
  298. incorporating assembler code into pascal code, and including inline
  299. statements in pascal program code.  Is there any more people would like to
  300. see?  E-mail me.  Also, I haven't gotten any comments from anyone
  301. about how I am doing.  Is anyone interested?  Email ggrotz@2sprint.net.
  302.  
  303. Note: I am sorry if I offended anyone by the "Final Statements for This
  304. Part" section.  I am apologizing in advance if I come off too harsh.
  305.